package me.mingshan.leetcode;

import java.util.HashMap;

/**
 * https://leetcode.cn/problems/subarray-sum-equals-k/
 * <p>
 * 560. 和为K的子数组
 * <p>
 * 给定一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。
 *
 * @author hanjuntao
 * @date 2025/8/23 0023
 */
public class L_560_和为K的子数组 {

    public static void main(String[] args) {
        // map value>1

        int[] nums = new int[]{1, -1, 0, 1};
        int k = 0;
        System.out.println(subarraySum2(nums, k));
    }

    /**
     * 暴力
     *
     * @param nums
     * @param k
     * @return
     */
    public static int subarraySum(int[] nums, int k) {
        int result = 0;

        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum == k) {
                    result++;
                }
            }
        }
        return result;
    }

    /**
     * 思路：
     * <p>
     * 假设数组为：
     * 1,2,3,4,5,6
     * <p>
     * 从一开始算时：
     * <p>
     * 1
     * 1,2
     * 1,2,3
     * 1,2,3,4
     * <p>
     * 从2开始算时：
     * 2
     * 2,3
     * 2,3,4
     * <p>
     * <p>
     * 3,
     * 3,4,5
     * <p>
     * 从计算2可以知道，计算2,3时，其实在计算1时，已经计算过1,2,3了,只不过需要将1的结果减去，即可以利用以前计算过的值
     * <p>
     * 算法思路：
     * <p>
     * 由于前缀和，我们可以很自然想到s[j]−s[i]=k的解的个数即为满足要求的子数组个数。
     * 此时就转化梦开始的地方：两数之和s[j]+(−s[i])=k！
     * 因此改写成方程：s[i]=s[j]−k，初始化一个哈希表来保存左边已经被遍历的元素。
     *
     *
     * <p>
     * https://leetcode.cn/problems/subarray-sum-equals-k/solutions/3626337/ling-shen-ti-jie-de-li-jie-geng-gua-he-x
     * -8cyr/
     *
     * @param nums
     * @param k
     * @return
     */
    public static int subarraySum2(int[] nums, int k) {
        //计算前缀和数组
        int len = nums.length;
        int[] preSum = new int[len + 1];
        preSum[0] = 0;
        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }

        // 转化为两数之和
        // 我们需要找到所有满足 preSum[j+1] - preSum[i] == k 的 (i, j) 对
        // 等价于 preSum[i] == preSum[j+1] - k
        int res = 0;

        // Key: 前缀和的值 (Integer)
        // Value: 该前缀和值出现的次数 (Integer)

        HashMap<Integer, Integer> preCnt = new HashMap<>();
        for (int sj : preSum) {
            int si = sj - k;
            // 已遍历元素中存在si
            if (preCnt.containsKey(si)) {
                // 加上相应的个数
                res += preCnt.get(si);
                System.out.println("sj: " + sj + " si: " + si + " res: " + res);
            }
            // 当前遍历结束，更新sj出现个数，便于后续判断使用
            preCnt.put(sj, preCnt.getOrDefault(sj, 0) + 1);

            System.out.println("sj: " + sj + " si: " + si + " preCnt: " + preCnt.get(sj));

            System.out.println("----------------");
        }

        return res;
    }

}
